%\section{Problema 3}
%\subsection{Introducción}
%\subsection{Desarrollo}
%\subsubsection{Correctitud}
%\subsection{Complejidad}
%\subsection{Casos Borde}
%\subsection{Casos de prueba y gráficos}

\section{Problema 3}

\subsection{Introducción}

En un museo se desea instalar un nuevo sistema de seguridad basado en sensores láser.

Cada piso del museo se encuentra modelado por una grilla de $n \times m$ casillas, donde cada casilla representa un metro cuadrado del mismo. 
No todas las casillas están libres, algunas contienen paredes.

El objectivo es colocar los sensores sobre el piso de modo tal que todas las casillas libres queden cubiertas por al menos un sensor de moviemiento.
Cuando un sensor se coloca sobre una casilla (libre, no pared) este cubre a la misma y a toda la fila y/o columna a la que pertenece.
Si la señal que emite el sensor colisiona con una pared, las casillas que se encuentren del otro lado de esta no quedarán cubiertas.
Hay varios tipos de sensores:

\begin{description}
	\item[Sensores bidireccionales] este tipo de sensor emite dos señales, puede ser colocado de forma tal que cubra una fila (horizontalmente, emite señales hacia la derecha e izquierda) o columna (verticalmente, emite señales hacia arriba y abajo). Cada sensor cuesta unos \$4.000.
	\item[Sensores cuatridireccionales] estos sensores emiten señales en cuatro direcciones, cubriendo fila y columna. El costo de cada sensor es de \$6.000.
\end{description}

Al colocarse los sensores, debe tenerse en cuenta que las señales emitidas por los mismos no pueden impactar sobre otros dispositivos. Tampoco se puede instalar más de un sensor en una casilla libre.

Existen algunos sectores del museo que deben ser reforzados.
Las casillas marcadas como importantes, deben ser cubiertas por las señales de dos sensores.

El objetivo es buscar una forma de ubicar los sensores, satisfaciendo lo anteriormente descripto, de forma tal que todas las casillas queden cubiertas y con el menor costo posible.
En caso de no encontrarse una solución, debe de indicarse.

\subsection{Desarrollo}

Para resolver el problema se pide utilizar la técnica de \emph{Backtracking}.

Se utiliza una matriz para representar la \emph{grilla}, cada elemento de la matriz se compone de una casilla la cual contiene información a cerca del estado de la misma, a saber:

\begin{itemize}
	\item ¿Contiene una pared?
	\item ¿Se encuentra ocupada por un sensor?¿De qué tipo?
	\item ¿Cuántas señales la cruzan (cubren)?
\end{itemize}

El algoritmo recorre esta matriz por filas buscando una casilla viable para colocar un sensor.
Una vez que la encuentra, modifica la/s casilla/s afectadas por el sensor.
Esto se repite hasta completar la grilla, eventualmente se encuentra una solución o no.
Si se encuentra se almacena, caso contrario no.
Tanto en uno u otro caso, se vuelve hacia atrás en la solución formada para probar otra combinación de sensores.

Ya que las posibles combinaciones de sensores que pueden obtenerse son demasiadas (dependiendo del tamaño del piso), se implementaron diferentes podas.

\subsubsection{Podas}

La primera poda tiene que ver con la posibilidad de resolver el problema con la instancia de piso dada.
Supongamos que tenemos un piso en donde existe una casilla marcada como importante, la misma se encuentra rodeada por dos paredes enfrentadas.
Siendo este el caso, no existe forma de cubrir la casilla con las señales de dos sensores.
Las paredes impiden que las señales atraviesen a la casilla.
Esto nos impide obtener una solución que cumpla con lo propuesto.

La segunda poda tiene que ver con el precio de la solución en cuestión.
Supongamos que nuestro algoritmo ya ha encontrado una solución factible y se encuentra generando otra combinación de sensores tratando de obtener otra.
Esta nueva combinación de sensores, ¿resulta ser de un mayor costo que la ya obtenida?
Si la respuesta es sí, no es prudente seguir desarrollando la solución.
De todas formas, será deshechada por ser más cara que la anteriormente obtenida.
Además todas las combinaciones que se desprenden de esta solución parcial seguirían costando más.

La última y más importante poda consiste en ir descartando los casilleros que están cubiertos por el rayo de un láser colocado previamente. Esto funciona debido a que no tiene sentido analizar una casilla así dado que la única opción es que quede libre (no podríamos poner otro láser más). Gracias a esta poda se produce una gran diferencia entre la cota de complejidad y el tiempo que lleva en correr realmente el algoritmo, ya que se reduce en gran cantidad las casillas para las cuales realizamos llamadas recursivas (analizaremos más en detalle esto en la sección 'Complejidad').


\subsubsection{Correctitud}

Al probar todas las distintas combinaciones de sensores, tarde o temprano encontraremos una solución (si existe).
Ahora bien, la forma en que elegimos dónde y cómo poner cada sensor puede llevarnos a soluciones incorrectas.
Debemos elegir las casillas apropiadamente siguiendo lo pedido por el problema.

En lugar de posicionar un sensor en una casilla y verificar la validez de la solución, se busca una casilla en la cuál sea válido colocar un sensor, a partir de la instancia de piso dada.

Las casillas son elegidas utilizando el siguiente criterio:

\begin{itemize}
	\item No contiene una pared,
	\item no contiene sensores colocados previamente,
	\item la casilla no se encuentra cubierta,
	\item y no es una casilla importante.
\end{itemize}

Los dos primeros puntos son bastante claros, son premisas que establece el problema (ver introducción).

La casilla se encuentra cubierta si se encuentra atravesada por la señal de un sensor, o de ser importante, por las señales de dos sensores.
Si la casilla se encuentra cubierta, significa que al poner un sensor sobre la misma estamos faltando a lo pedido. El problema estipula que la señal de un sensor no debe impactar contra otro dispositivo.

Si la casilla en cuestión es importante, tenemos un problema.
Supongamos que colocamos un sensor sobre la misma.
Quedaría cubierta por una señal, pero no podríamos colocar otro sensor.
La señal colisionaría con el dispositivo ubicado sobre el sitio importante.

Dependiendo del sensor que queramos colocar, debemos verificar que no existan otros dispositivos cuales puedan interferir con su señal.
Si es cuatridireccional debemos recorrer la fila/columna de la casilla elegida para verificar la no existencia de dispositivos.
Si es bidireccional debemos verificar fila o columna dependiendo de la orientación elegida (vertical u horizontal).

Al llegar a una instancia recursiva del problema donde tanto colocar alg\'un sensor como no hacerlo nos dan una instancia inv\'alida del piso del museo, el algoritmo retorna a la funci\'on que lo ejecut\'o. Esta restaura el piso al estado anterior a haber ejecutado la \'ultima movida, quita el \'ultimo sensor agregado a la lista soluci\'on y entra en la siguiente instancia del for en la cual, repite la operaci\'on anterior para el siguiente sensor posible que a\'un no probamos. Si ya realizamos esto para todos los sensores disponibles sin poder agregar ninguno a nuestra soluci\'on, el algoritmo se llama recursivamente avanzando a la pr\'oxima casilla libre y dejando la casilla actual vac\'ia. Si no hay m\'as casillas libres, el algoritmo indica que estamos en una instancia inv\'alida y retorna a la funci\'on que lo llam\'o. Al retornar, va a volver hasta la \'ultima llamada recursiva en la cual todav\'ia es posible modificar algo en el piso. Si vuelve hasta la primer llamada (la llamada original) quiere decir que la instancia del problema no tiene soluci\'on, ya que no hay m\'as posibles modificaciones que puedan hacerse para lograr una combinaci\'on v\'alida de sensores. Esto demuestra que nuestro algoritmo recorre todas las instancias posibles y que por lo tanto, encuentra la soluci\'on al problema en caso de existir o informa que no existe soluci\'on alguna.

Finalmente, un piso se encuentra cubierto si todas las casillas están cubiertas.
Una combinación de sensores que cumpla con lo anterior se almacena como solución.
Cada vez que se encuentre una solución, esta reemplazará a una ya existente si es más barata.
De esta forma nos aseguramos de quedarnos con la mejor solución al problema.

La demostraci\'on de que las podas de nuestro algoritmo no dejan afuera ninguna posible solución óptima se encuentra en la sección 'Podas'.

\subsection{Análisis de complejidad}

\begin{algorithm}
	%\DontPrintSemicolon
	\SetKwInOut{Input}{input}
	\SetKwInOut{Output}{ouput}
	\SetKwComment{Complejidad}{\color{Blue}$\rhd$ $\mathcal O($}{\color{Blue}$\mathcal )$}
	\SetKwComment{SubComplejidad}{\color{Red}$\square$ $\mathcal O($}{\color{Red}$\mathcal )$}
	\SetKwComment{SubSubComplejidad}{\color{Fuchsia}$\fullmoon$ $\mathcal O($}{\color{Fuchsia}$\mathcal )$}
	\SetKwComment{ComplejidadTotal}{\color{Blue}Complejidad total $\rhd$ $\mathcal O($}{\color{Blue}$\mathcal )$}
	\SetKwComment{SubComplejidadTotal}{\color{Red}Complejidad total $\square$ $\mathcal O($}{\color{Red}$\mathcal )$}
	\SetKwComment{SubSubComplejidadTotal}{\color{Fuchsia}Complejidad total $\fullmoon$ $\mathcal O($}{\color{Fuchsia}$\mathcal )$}

	%\SetKwData{S}{S}
	%\SetKwData{A}{A}
	%\SetKwData{n}{n}
	\BlankLine
	\Input{Grilla de $n \times m$}
	\Output{Lista de tupla sensor, coordenada}

	\BlankLine
	\If(\Complejidad*[f]{\color{Blue}$n \cdot m$}){Piso cubierto por sensores.}
	{
		\If(\Complejidad*[f]{\color{Blue}$1$}){No existe mejor solución.}
		{
			Asignar solución actual como mejor solución. \Complejidad*[r]{\color{blue}$1$}
			Terminar.
		}
		\If(\Complejidad*[f]{\color{Blue}$1$}){Existe mejor solución y es más costosa.}
		{
			Reemplazar mejor solución por actual. \Complejidad*[r]{\color{blue}$1$}
			Terminar.
		}
	}
	\Else
	{
		\If(\Complejidad*[f]{\color{Blue}$1$}){Existe mejor solución y es menos costosa que la solución parcial actual.}
		{
			Terminar
		}
	}

	\BlankLine
	Buscar casilla libre para colocar sensor. \Complejidad*[r]{\color{blue}$n \cdot m$}
	\BlankLine

	\For(\Complejidad*[f]{\color{Blue}$1$}){Cada sensor posible}
	{
		\If(\Complejidad*[f]{\color{Blue}$n + m$}){Casilla libre elegida sin interferencia de otros dispositivos.}
		{
			Colocar sensor en el piso. \Complejidad*[f]{\color{Blue}$n + m$}\\
			Agregar a solución actual el sensor en cuestión. \Complejidad*[f]{\color{Blue}$1$}\\
		}
		\Else
		{
			Saltar a siguiente sensor.
		}
		Llamada recursiva a la función. \Complejidad*[f]{\color{Blue}$1$}\\
		Restaurar el piso al estado anterior a colocar el sensor. \Complejidad*[f]{\color{Blue}$n + m$}\\
		Quitar último elemento de la solución. \Complejidad*[f]{\color{Blue}$1$}
	}
	\BlankLine
	Llamada recursiva a la función, la casilla de esta iteración se deja libre. \Complejidad*[f]{\color{Blue}$1$}\\
	Terminar.

	\caption{Ejercicio 3 - Complejidad}
\end{algorithm}

Para verificar que el piso se encuentre cubierto, se recorre por completo la matriz que le conforma.
Por lo tanto la complejidad es de $\mathcal O(n \cdot m)$.

La solución es una lista enlazada y un entero con el costo total de la misma.
Obtener el precio, agregar y quitar elementos de la misma toma tiempo constante.

Buscar una casilla libre cuesta $\mathcal O(n \cdot m)$.
Potencialmente se deberán recorrer todas las casillas.
Verificar si la casilla está disponible, es constante, ya que tenemos la información actualizada y de fácil acceso en cada una de ellas.

Para buscar sensores que interfieran con el que vamos a colocar, debemos recorrer fila y/o columna.
Esto nos da una complejidad de $\mathcal O(n + m)$.

Actualizar el piso luego de haber colocado un sensor, también tiene un costo de $\mathcal O(n + m)$. Ya que sólo debemos recorrer fila y/o columna afectada.

Para cada casilla libre se realizan cuatro llamadas recursivas. Para realizar el análisis de complejidad vamos a suponer que todas las casillas están siempre libres aunque en la práctica esto nunca se cumple debido a las podas implementadas.

El análisis de complejidad queda expresado de la siguiente forma.

Consideremos $N = n \times m$.

\begin{center}
$T(N) = 4 \times T(N - 1) + N \Longleftrightarrow$

$T(N) = 4 \times T(4 \times T(N - 2) + N) + N \Longleftrightarrow$

$\cdots$

$T(N) = 4^N \times T(1) + \sum_{i=0}^{N-1} (4^i \times N) \Longleftrightarrow$

$T(N) = 4^N + N \times \frac{4^{(N-1)} - 1}{4 - 1} \Longleftrightarrow$

$T(N) \le 4^N + N \times 4^N$
\end{center}

Tomando el máximo de la suma, obtenemos como cota de complejidad máxima $\mathcal O(N \times 4^N)$.

\subsection{Análisis de casos}

Las siguientes instancias de \emph{piso} fueron puestas a prueba.

\begin{itemize}
\item Caso nulo. Al no tener casillas libres devuelve ``$-1$''.

\begin{multicols}{2} 
\begin{verbatim}
Input:
0
\end{verbatim}
\begin{verbatim}
Output:
-1
\end{verbatim}
\end{multicols}

\item Caso piso $1 \times 1$, libre. La solución es más que obvia, devolverá el sensor menos costoso.

\begin{multicols}{2} 
\begin{verbatim}
Input:
1 1
1
\end{verbatim}
\begin{verbatim}
Output:
1 4000
2 1 1
\end{verbatim}
\end{multicols}

\item Caso piso $4 \times 4$, todo libre. Aquí la opción menos costosa en colocar sensores bidireccionales (todos horizontales o todos verticales).

\begin{multicols}{2} 
\begin{verbatim}
Input:
4 4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
\end{verbatim}
\begin{verbatim}
Output:
4 16000
2 1 1
2 2 1
2 3 1
2 4 1
\end{verbatim}
\end{multicols}

\item Caso piso $1 \times 1$, pared. Devolverá ``$-1$'' ya que no hay dónde colocar sensores.

\begin{multicols}{2} 
\begin{verbatim}
Input:
1 1
0
\end{verbatim}
\begin{verbatim}
Output:
-1
\end{verbatim}
\end{multicols}

\item Caso piso $4 \times 4$, todo pared. Variación del anterior, mismo resultado.

\begin{multicols}{2} 
\begin{verbatim}
Input:
4 4
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
\end{verbatim}
\begin{verbatim}
Output:
-1




\end{verbatim}
\end{multicols}

\item Caso piso $1 \times 1$, importante. Devolverá ``$-1$'' no es posible colocar más de un sensor y se necesitan por lo menos dos.

\begin{multicols}{2} 
\begin{verbatim}
Input:
1 1
2
\end{verbatim}
\begin{verbatim}
Output:
-1
\end{verbatim}
\end{multicols}

\item Caso piso $4 \times 4$, todo importante. Variación del anterior, mismo resultado.

\begin{multicols}{2} 
\begin{verbatim}
Input:
4 4
2 2 2 2
2 2 2 2
2 2 2 2
2 2 2 2
\end{verbatim}
\begin{verbatim}
Output:
-1




\end{verbatim}
\end{multicols}



\item Caso piso $4 \times 4$, importante entre paredes. Dijimos que si pasaba esto, no había solución por lo que debe devolver ``$-1$''.

\begin{multicols}{2} 
\begin{verbatim}
Input:
4 4
1 1 1 1
1 0 2 0
1 1 1 1
1 1 1 1
\end{verbatim}
\begin{verbatim}
Output:
-1




\end{verbatim}
\end{multicols}

\item Caso piso $5 \times 5$, caso al azar.
La solución a este caso fue estudiada, se llego a la conclusión de que es la solución menos costosa.

\begin{multicols}{2} 
\begin{verbatim}
Input:
5 5
1 1 1 0 1
1 1 1 0 1
1 1 1 2 1
1 1 1 1 1
1 1 1 0 1
\end{verbatim}
\begin{verbatim}
Output:
5 22000
3 1 1
3 1 2
3 1 3
1 3 5
3 4 4
\end{verbatim}
\end{multicols}
\end{itemize}



\subsection{Caso especial: Tablero de Ajedrez}

Analizamos el caso particular de un piso de museo dispuesto como un tablero de ajedrez, donde las casillas negras representan paredes y las blancas una baldosa de piso libre (sin ningún rombo). Tenemos la teoría de que este escenario representaría el peor caso en cuanto a la resolución del algoritmo. Las casillas libres aisladas bloquean la posibilidad de que el algoritmo realice una poda descartando las casillas tocadas por un láser. Por lo tanto, para todas las casillas libres (que son exactamente (n*m)/2) el algoritmo prueba cada una de las cuatro posibilidades. La complejidad en este caso es exactamente $O((N/2) \times 4^{N/2})$, y la cota es considerablemente más certera debido a que descartamos las podas que realizaba el algoritmo.

No podemos probar formalmente que éste es el peor caso aunque realizamos una prueba experimental contra pisos sin paredes y contra paredes generadas aleatoriamente. Descartamos las ``casillas importantes'' porque no podemos incluirlas en el caso del tablero de ajedrez y queremos garantizar cierta simetría entre los experimentos. En esta prueba experimental encontramos que efectivamente el caso del tablero de ajedrez supera ampliamente a los otros dos casos, lo que ofrece un argumento a favor de nuestra teoría.

\begin{center}
    \includegraphics[scale=0.6]{./img/nuevacota.png} \\
     \small{Comparación del algoritmo en los distintos casos planteados}
    \label{fig:cotaPro3}
\end{center}

Realizamos también un gráfico con los resultados promedio que obtuvimos en el test de performance comparando la cota $O(N \times 4^{N})$ demostrada teóricamente con la que proponemos a partir del análisis de este caso de $O((N/2) \times 4^{N/2})$.

\begin{center}
    \includegraphics[scale=0.6]{./img/analisis3bis.png} \\
     \small{Comparación de ambas cotas teóricas}
    \label{fig:cotaPro3}
\end{center}

Si fuera posible demostrar que éste es el peor caso del algoritmo, estaríamos en condiciones de reducir la cota de complejidad a $O((N/2) \times 4^{N/2})$, dado que estaríamos demostrando que no existe ningún caso con complejidad superior. Por eso nos parece un caso digno de análisis y le hacemos una mención especial.


\subsection{Test de performance}

El test realizado consiste en resolver pisos de diferentes tamaños.
El objetivo es ver el impacto que tiene la dimensión del mismo en el tiempo de ejecución.
Además de comparar los datos obtenidos con la cota de complejidad teórica calculada anteriormente.

Realizar este test en pisos que no se encuentren vacíos traen un inconveniente.
El hecho de que existan paredes o sitios importantes y se encuentren dispuestas de diferentes maneras, afecta las decisiones tomadas para generar las soluciones parciales en el bactracking.
Esto puede conducir a que el algoritmo tarde más o menos de lo que haría si no las tuviera.
No es posible mantener una relación entre el tamaño y las disposición de los objetos (pared o sitio importante) de forma tal que no afecte el experimento.

En la figura ~\ref{fig:cotaPro3} se muestran los resultados de la prueba.

\begin{center}
    \includegraphics[scale=0.6]{./img/compComplejidad3.png}    \\
     \small{Comparación cota complejidad contra tiempo de ejecución reales - Escala lineal}
    \label{fig:cotaPro3}
\end{center}


\begin{center}
    \includegraphics[scale=0.6]{./img/ej3bla.png}    \\
     \small{Comparación cota complejidad contra tiempo de ejecución reales - Escala logarítmica}
    \label{fig:cotaPro3}
\end{center}


La cota de complejidad es muy superior a los resultados arrojados por el test.
Esto se debe a que las podas efectuadas optimizan y disminuyen la cantidad de resultados que la aplicación analiza.
Ejemplificando... si tenemos una línea de casilleros libres y se coloca un sensor bidireccional de forma que la cubra, la próxima casilla elegida luego del llamado recursivo será la primera libre de las subsiguientes filas.
El algoritmo asume que la fila, ahora cubierta, no es candidata a poner más sensores.

Los resultados de la figura ~\ref{fig:cotaPro32} reflejan el porque de la utilización de pisos vacíos.
El experimento se realizó con un piso de igual tamaño ($5 \times 5$) al que se le fueron agregando paredes en lugares aleatorios.
Al principio como la cantidad casillas tipo pared era menor en relación a la cantidad de casilleros libres, el tiempo de ejecución fue en aumento.
La ubicación de las paredes hacía necesaria la utilización de más sensores en comparación con su contraparte vacía.
Cuando la cantidad de casillas tipo pared fue más grande y la cantidad de casilleros libres fue mucho menor, el tiempo de ejecución fue notablemente más pequeño.

\begin{center}
    \includegraphics[scale=0.6]{./img/analisis3.png}    \\
     \small{Relación tiempo ejecución en función de cantidad de casillas ``pared'', piso de $5 \times 5$. 50 iteraciones por instancia}
    \label{fig:cotaPro32}
\end{center}

Una posible interpretación de este fenómeno es que como las paredes están puestas aleatoriamente, cuando hay menos de siete, funcionan para restringir la poda que realiza el algoritmo al poner un sensor y por lo tanto éste debe analizar más casos (poner más sensores). A medida que hay más paredes puestas aleatoriamente, sin embargo, aumenta la posibilidad de que las paredes se agrupen en bloques y no necesariamente restrinjan la poda que realiza el algoritmo, pero que si sirvan para eliminar casillas que el algoritmo no va a considerar porque no son casillas libres.


\subsection{Compilar y ejecutar}

Para utilizar la aplicación, primero debe compilarse utilizando el \emph{Makefile} que se encuentra en la carpeta \emph{src}.
El binario será generado en una sub-carpeta llamada \emph{bin}, con el nombre \emph{nocheMuseo}.

En el caso de compilar en Windows, se requiere tener correctamente instalado MinGW o similar.
La generación del ejecutable se realiza de la manera anteriormente nombrada.

La aplicación toma el archivo con los parámetros de entrada por redirección de entrada.
Desde consola la forma de proceder es la siguiente:

\begin{center}
\begin{multicols}{2} 
\begin{verbatim}
Linux
$ ./nocheMuseo < input.txt
\end{verbatim}
\begin{verbatim}
Windows
C:\> nocheMuseo.exe < input.txt
\end{verbatim}
\end{multicols}
\end{center}
